import entity.TreeNode;

public class LowestCommonAncestorOfBST {
    /*
    * 235. 二叉搜索树的最近公共祖先
    * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
    * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，
    * 最近公共祖先表示为一个结点 x，
    * 满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
    *
    * 所有节点的值都是唯一的。
    * p、q 为不同节点且均存在于给定的二叉搜索树中。
    * */
    public static void main(String[] args){

    }

    // 我的想法：和二叉树的最近公共祖先一样的解法就行，
    // 但既然给了这题， 肯定得利用一下二叉搜索树的特性
    // 从头节点开始向下遍历，如果第一次遇到某节点的值在pq之间，那么该节点一定是结果
    public TreeNode mySolution(TreeNode root, TreeNode p, TreeNode q){
        // 先令p < q, 便于判断
        if(p.val > q.val){
            TreeNode temp = p;
            p = q;
            q = temp;
        }
        return dfs(root, p, q);
    }

    private TreeNode dfs(TreeNode root, TreeNode p, TreeNode q){
        // 遇到夹在中间的了，就是他！返回！
        if(root.val <= q.val && root.val >= p.val)
            return root;
        if(root.val < p.val)
            return dfs(root.right, p, q);
        else
            return dfs(root.left, p, q);
    }

    // 其实不用排序。。。。
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root.val > p.val && root.val > q.val) lowestCommonAncestor(root.left, p, q);
        if(root.val < p.val && root.val < q.val) lowestCommonAncestor(root.right, p, q);
        return root;
    }
}
